package day53_416;

import java.lang.annotation.Target;
import java.util.Arrays;

/**
 * @ClassName Solution
 * @Description DFS解法
 * @Author clockTown
 * @Date 2021/7/1 20:36
 * @Version 1.0
 */
public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //如果sum为奇数或数组长度为1，返回false
        if (sum % 2 == 1 || nums.length == 1) {
            return false;
        }
        sum = sum / 2;
        Arrays.sort(nums);
        //如果数组最大值大于总和的一半，返回false
        if (nums[nums.length - 1] > sum) {
            return false;
        }
        return dfs(nums, sum, sum, 0);
    }

    /**
     * 如果 nums 中最大值 > 2/sum, 那么肯定无解
     * 在搜索过程中，我们对每个数都是取或者不取，并且数组中所有项都为正数。我们设取的数和为 pickedSum，不难得 pickedSum <= 2/sum， 同时要求丢弃的数为 discardSum，不难得 pickedSum <= 2 / sum。
     * 被取的数之和或者不被取的数之和，这两个值只要有一个为数组总和的一半，就说明数组可以被分为两份
     * @param nums 数组
     * @param pickRemain 被取的数之和
     * @param discardRemain 被抛弃的数之和
     * @param idx 索引
     * @return
     */
    private boolean dfs(int[] nums, int pickRemain, int discardRemain, int idx) {
        if (pickRemain < 0 || discardRemain < 0 || idx >= nums.length) {
            return false;
        }

        return pickRemain == 0 || discardRemain == 0 || dfs(nums, pickRemain - nums[idx], discardRemain, idx + 1) || dfs(nums, pickRemain, discardRemain - nums[idx], idx + 1);
    }
}
